package com.breeze.leetcode

import java.util.*

/**
 * https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
 * 104. 二叉树的最大深度
 * 给定一个二叉树，找出其最大深度。
 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 * 说明: 叶子节点是指没有子节点的节点。
 */
class LeetCode104 {
    /**
     * 1. 递归法  也就是DFS 深度优先搜索
     * 时间复杂度： O(N)，N是节点的数量，每个节点都会访问一次
     * 空间复杂度： O(log(N)) 递归次数为log(N)
     */
    fun maxDepth(root: TreeNode?): Int {
        if (root == null) return 0
        // 左子树深度
        val lDepth = maxDepth(root.left)
        // 右子树深度
        val rDepth = maxDepth(root.right)
        // 左右子树最大深度+1(根节点)即为当前树深度
        return lDepth.coerceAtLeast(rDepth) + 1
    }

    /**
     * 2. 迭代法 通过BFS 宽度优先搜索
     * 时间复杂度： O(N)
     * 空间复杂度： O(N)
     */
    fun maxDepth1(root: TreeNode?): Int {
        if (root == null) return 0
        var depth = 0
        val queue = LinkedList<TreeNode>()
        queue.add(root)
        while (!queue.isEmpty()) {
            depth++
            for (i in 0 until queue.size) {
                val node = queue.poll()
                if (node.left != null) {
                    queue.add(node.left!!)
                }
                if (node.right != null) {
                    queue.add(node.right!!)
                }
            }
        }
        return depth;
    }
}

class TreeNode(var `val`: Int) { // ``特殊符号用于将一个不合法的字符变为合法
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun main() {
    val treeNode = TreeNode(3)
    treeNode.left = TreeNode(9)
    treeNode.right = TreeNode(20)
    treeNode.right?.left = TreeNode(15)
    treeNode.right?.right = TreeNode(7)
    val leetCode104 = LeetCode104()
    println(leetCode104.maxDepth1(treeNode))
}
